/*
 *  levelUpGame - AStarPathFinder.h
 *  Copyright 2011 W. Reckman. All rights reserved.
 *
 * NOTES
 * - A simple tutorial on A* pathfinding: http://www.policyalmanac.org/games/aStarTutorial.htm
 */
#ifndef A_STAR_PATH_FINDER_H
#define A_STAR_PATH_FINDER_H

#include <queue>
#include "ofTypes.h"
#include "AStarNode.h"

class LevelUpApp;
class GameModel;

//NOTE: this defines the cost of a path with the other ghost on it
#define CROSS_GHOST_EDGE_PENALTY 10000.0f

//--------------------------------------------------------------
template <typename T>
struct AStarNodeP_equal
{
	const T* to_find;
	
	bool operator()( const T* other ) const {
		return *to_find == *other;
	}
};

//--------------------------------------------------------------
/* NOTE: this subclass is quite ugly. */
class PriorityQueue_NodeP : public std::priority_queue<AStarNode*, std::vector<AStarNode*>, AStarNodeFCompare> {
public:
	void clear();
	void clearWithDelete();
	bool remove( AStarNode* p_ );
	AStarNode* findWithPValue( const AStarNode* node_ );
	const AStarNode* operator[]( int index ) const;
};

//--------------------------------------------------------------
class AStarPathFinder {
public:
	typedef std::vector<AStarNode*> vec_AStarNodeP;
	typedef std::vector<ofPoint> vec_ofPoint;
	
	explicit AStarPathFinder( const LevelUpApp& appRef_ );
	
	int getDistance(  const ofPoint& from_, const ofPoint& to_  );
	vec_ofPoint findPath( const ofPoint& from_, const ofPoint& to_, const ofPoint* otherGhost_ = 0 );
	
	void draw() const;
	
private:
	const LevelUpApp& appRef;
	const GameModel& game;
	PriorityQueue_NodeP openSet;
	vec_AStarNodeP closedSet;
	
	/* prohibit copying */
	AStarPathFinder( const AStarPathFinder& other_ );
	const AStarPathFinder& operator=( const AStarPathFinder& other_ );
	
	vec_ofPoint constructPath( AStarNode* endNode_ );
	vec_AStarNodeP getNeighbours( AStarNode* node_, AStarNode* tgt_, AStarNode* otherGhost_, int margin_, bool wrapVertical_ = true ) const;
	int findPointInEdges( const GridPoint<int>& p_, const GridPoint<int>& edgeSrc_, const vec_AStarNodeP& edgeDests_, int margin_ ) const;
};

#endif /* ! A_STAR_PATH_FINDER_H */
